{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Nth Digit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findNthDigit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 N 位数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code> ，请你在无限的整数序列&nbsp;<code>[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]</code> 中找出并返回第&nbsp;<code>n</code><em> </em>位上的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 11\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 <strong>0 </strong>，它是 10 的一部分。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nth-digit](https://leetcode.cn/problems/nth-digit/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nth-digit](https://leetcode.cn/problems/nth-digit/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '11']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        p=9\n",
    "        t=1\n",
    "        x=p*t\n",
    "        while n>=x:\n",
    "            n-=x\n",
    "            p*=10\n",
    "            t+=1\n",
    "            x=p*t\n",
    "        if n==0:\n",
    "            return 9\n",
    "        y=n//t\n",
    "        z=n%t\n",
    "        if z==0:\n",
    "            tar=pow(10,t-1)+y-1\n",
    "        else:\n",
    "            tar=pow(10,t-1)+y\n",
    "        tar=str(tar)\n",
    "        return int(tar[(z-1+t)%t])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 计算出结果的位数, 数字和该数字的第几位\n",
    "        bit, base = 1, 9\n",
    "        # 一位数有9个, 二位数有2*90个, 三位数有3*900个\n",
    "        while n > bit * base:\n",
    "            n -= bit * base\n",
    "            bit += 1\n",
    "            base *= 10\n",
    "        # 因为从0开始计数(10, 100, 1000), 要-1\n",
    "        n -= 1\n",
    "        # 计算数字\n",
    "        num = 10 ** (bit - 1) + n // bit\n",
    "        # 计算在该数字的多少位\n",
    "        idx = n % bit\n",
    "        return num // (10 ** (bit - idx - 1)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        ls = 1 # 字符串初始长度\n",
    "        base = 1\n",
    "        while base * 9 * ls < n:\n",
    "            n -= base * 9 * ls\n",
    "            ls += 1\n",
    "            base *= 10\n",
    "        start = 10**(ls-1) # 当前范围内的最小值\n",
    "        index = n - 1 # 当前位在开始位的索引，如果为10，应该是10-9后的第1位，索引为0\n",
    "        num = start + index // ls # 寻找第多少个数字\n",
    "        digit = index % ls # 第多少个数字的第几位\n",
    "        # print(f\"num:{num}, digit:{digit}, {num // (10**(ls-digit - 1))}\")\n",
    "        return (num // (10**(ls-digit - 1))) % 10 # 12345,假入第三位，应该除到123然后取10的余得到3\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9\n",
    "        while n > d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        index = n - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d\n",
    "        digitIndex = index % d\n",
    "        # return num // 10 ** (d - digitIndex - 1) % 10\n",
    "        return int(str(num)[digitIndex])\n",
    "\n",
    "# class Solution:\n",
    "#     def findNthDigit(self, n):\n",
    "#         length = 1  # 当前数（十进制）的位数\n",
    "#         weight = 1  # 当前位的权重（10^i）\n",
    "\n",
    "#         while n > 9 * weight * length:\n",
    "#             n -= 9 * weight * length\n",
    "#             length += 1\n",
    "#             weight *= 10\n",
    "\n",
    "#         curNum = (n - 1) // length + weight  # curNum是包含所找digit的那个数，整个数列的第一个数是1\n",
    "#         resDigit = 0\n",
    "\n",
    "#         for i in range((n - 1) % length, length):\n",
    "#             resDigit = curNum % 10\n",
    "#             curNum //= 10\n",
    "\n",
    "#         return resDigit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9 9\n",
    "        # 10-99 90\n",
    "        # 100-999 900\n",
    "        scale = 1\n",
    "        dn = 1\n",
    "        while n >= 10 * scale * dn:\n",
    "            n -= 9 * scale * dn\n",
    "            scale *= 10\n",
    "            dn += 1\n",
    "        return self.find_now(n, scale, dn)\n",
    "    \n",
    "    def find_now(self, n, scale, dn):\n",
    "        #1 2 1 0\n",
    "        #2 3 1 1\n",
    "        #3 4 2 0\n",
    "        n1 = (n+dn-1) // dn\n",
    "        n2 = (n+dn-1) % dn\n",
    "        st = scale\n",
    "        n = scale + n1 - 1\n",
    "        #return n1, n2, st, n\n",
    "        for _ in range(dn-1-n2):\n",
    "            n //= 10\n",
    "        return n % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        firststate = 1\n",
    "        count = 0  \n",
    "        temp = n\n",
    "        while temp > firststate * 9 * 10 **(firststate-1):\n",
    "            temp -=  firststate * 9 * 10 **(firststate-1)\n",
    "            count += 9 * 10 **(firststate-1)\n",
    "            firststate += 1\n",
    "        #找到在哪个9的范围内\n",
    "        #减掉前面的数字个数：就是count\n",
    "        count += temp//firststate\n",
    "        if temp % firststate:\n",
    "            return int(str(count+1)[(temp%firststate)-1])\n",
    "        else:\n",
    "            return int(str(count)[-1])\n",
    "        #找到实在哪个数字上\n",
    "        #返回这个数字某个位"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        count = 9\n",
    "        start = 1\n",
    "        while count < n:\n",
    "            n -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = digit * 9 * start\n",
    "        num = start + (n-1) // digit\n",
    "        res = int(str(num)[(n-1) % digit])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit,start,count=1,1,9\n",
    "        while n>count:\n",
    "            n-=count\n",
    "            start*=10\n",
    "            digit+=1\n",
    "            count=9*start*digit\n",
    "        num=start+(n-1)//digit\n",
    "        return int(str(num)[(n-1)%digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        start, digit, count = 1,1,9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9*start*digit\n",
    "        nums = start + (n-1)//digit\n",
    "        res = str(nums)[(n-1)%digit]\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit=1\n",
    "        base=9\n",
    "        while n>digit*base:\n",
    "            n-=digit*base\n",
    "            digit+=1\n",
    "            base*=10\n",
    "        n-=1\n",
    "        num=10**(digit-1)+n//digit\n",
    "        index=n%digit\n",
    "        return int(str(num)[index])\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        for i in range(1, 11):\n",
    "            n -= i * 9 * (10 ** (i - 1))\n",
    "            if n < 0:\n",
    "                n += i * 9 * (10 ** (i - 1))\n",
    "                break\n",
    "    # i代表i位数 n表示在i位数上的位次\n",
    "        if n==0:\n",
    "            i-=1\n",
    "            res_int=10**i-1\n",
    "            res_lst=list(str(res_int))\n",
    "            result=res_lst[-1]\n",
    "        else:\n",
    "            start = 10 ** (i - 1)\n",
    "            x = n // i\n",
    "            y = n % i\n",
    "            if x == 0:\n",
    "                res_int = start\n",
    "                res_lst = list(str(res_int))\n",
    "                result = res_lst[y-1]\n",
    "            elif x!=0 and y==0:\n",
    "                res_int = start+x-1\n",
    "                res_lst = list(str(res_int))\n",
    "                result = res_lst[-1]\n",
    "            elif x!=0 and y!=0:\n",
    "                res_int = start+x\n",
    "                res_lst = list(str(res_int))\n",
    "                result = res_lst[y-1]\n",
    "        return int(result)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9  9  9*1\n",
    "        # 10-99 90 90*2\n",
    "        # 100-999 900 900*3\n",
    "\n",
    "        # 定位到是几位数后，以3位数为例，如果是1，就是100的1，如果是4，就是101的第一个1\n",
    "        # 具体来说%3 /3分别得到两个索引\n",
    "        # 按以上模拟即可\n",
    "        d, count = 1, 9 # d 和 count 分别表示当前遍历到的位数和当前位数下的所有整数数量\n",
    "        while n > d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        # 循环结束后，d为n所在的位数， n为位数内的位数索引（从1开始）\n",
    "        # print(n)\n",
    "        start = 10 ** (d - 1) # 1 10 100 1000 ... n所在的位数的最小数\n",
    "        num = start + (n - 1) // d  # 一个数d位, 所以//d\n",
    "        digitIndex = (n - 1) % d    # num内的位数索引，从0开始，所以n要减1\n",
    "        return int(str(num)[digitIndex])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        num_len=1\n",
    "        section_cnt=9\n",
    "        remain_n=n\n",
    "        while num_len*section_cnt<remain_n:\n",
    "            remain_n-=num_len*section_cnt\n",
    "            num_len+=1\n",
    "            section_cnt*=10\n",
    "        cur_section_begin=section_cnt//9\n",
    "        target_num=cur_section_begin+(remain_n-1)//num_len\n",
    "        idx=(remain_n-1)%num_len\n",
    "        return int(str(target_num)[idx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = 9 * digit * start\n",
    "        num = start +  (n - 1) // digit\n",
    "        s = str(num)\n",
    "        res = int(s[(n - 1) % digit])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur, base = 1, 9\n",
    "        while n > cur * base:\n",
    "            n -= cur * base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "\n",
    "        a = n / cur\n",
    "        b = n % cur\n",
    "\n",
    "        num = 10 ** ( cur - 1 ) + a - 1\n",
    "\n",
    "        test_v = str(num)[cur -1] if(b == 0) else str(num+1)[b-1]\n",
    "        return (int)(test_v)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9           #d：位数；count：\n",
    "        while n > d * count:       #d * count：d位数字共有9*10**（d-1）个\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        index = n - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d   #找到n属于第几个数\n",
    "        digitIndex = index % d     #找到n属于的数字的第几位\n",
    "        # return num // 10 ** (d - digitIndex - 1) % 10\n",
    "        return int(str(num)[digitIndex])\n",
    "\n",
    "# class Solution:\n",
    "#     def findNthDigit(self, n):\n",
    "#         length = 1  # 当前数（十进制）的位数\n",
    "#         weight = 1  # 当前位的权重（10^i）\n",
    "\n",
    "#         while n > 9 * weight * length:\n",
    "#             n -= 9 * weight * length\n",
    "#             length += 1\n",
    "#             weight *= 10\n",
    "\n",
    "#         curNum = (n - 1) // length + weight  # curNum是包含所找digit的那个数，整个数列的第一个数是1\n",
    "#         resDigit = 0\n",
    "\n",
    "#         for i in range((n - 1) % length, length):\n",
    "#             resDigit = curNum % 10\n",
    "#             curNum //= 10\n",
    "\n",
    "#         return resDigit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count: # 1.\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit # 2.\n",
    "        return int(str(num)[(n - 1) % digit]) # 3.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        start = 1\n",
    "        base = 9\n",
    "        while n > base:\n",
    "            n -= base\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            base = start * digit * 9\n",
    "\n",
    "        number = start + (n - 1) // digit\n",
    "        digit_idx = (n - 1) % digit\n",
    "        return int(str(number)[digit_idx])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        i = 1\n",
    "        left, right = 1, 10\n",
    "        while True:\n",
    "            if n < right: break \n",
    "            left = right\n",
    "            right = right + 9 * pow(10, i) * (i + 1)\n",
    "            i += 1\n",
    "        num = pow(10, i - 1) + (n - left) / i \n",
    "        num_str = \"%d\" % num \n",
    "        return ord(num_str[(n - left) % i]) - ord('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, base = 1, 9\n",
    "        while n > d * base:\n",
    "            n -= d * base\n",
    "            d += 1\n",
    "            base *= 10\n",
    "        num = 10 ** (d-1) - 1 + math.ceil(n/d)\n",
    "        idx = (n-1) % d\n",
    "        return int(str(num)[idx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        n_digit=1\n",
    "        sum_digits=0\n",
    "        while True:\n",
    "            cur_digits_count=9*n_digit*pow(10,n_digit-1)\n",
    "            if sum_digits+cur_digits_count<n:\n",
    "                sum_digits+=cur_digits_count\n",
    "                n_digit+=1\n",
    "            else:\n",
    "                skip_nums=(n-1-sum_digits)//n_digit\n",
    "                last_num=pow(10,n_digit-1)+skip_nums\n",
    "                s=str(last_num)\n",
    "                return int(s[n-sum_digits-n_digit*skip_nums-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        i = 0\n",
    "        while n > 9 * (i + 1) * pow(10, i):\n",
    "            n -= 9 * (i + 1) * pow(10, i)\n",
    "            i += 1\n",
    "\n",
    "        start = 10 ** i + (n - 1) // (i + 1)\n",
    "        n = n - (n - 1) // (i + 1) * (i + 1)\n",
    "        return int(str(start)[n-1])\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit\n",
    "        s = str(num)\n",
    "        res = int(s[(n - 1) % digit])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit\n",
    "        return int(str(num)[(n - 1) % digit])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        k = 1\n",
    "        num = 0\n",
    "        while(n > pow(10, k-1) * 9 * k):\n",
    "            n -= pow(10, k-1) * 9 * k\n",
    "            num += pow(10, k-1) * 9\n",
    "            k += 1\n",
    "        num += n // k\n",
    "        if (n % k == 0):\n",
    "            return ord(str(num)[-1]) - ord(\"0\")\n",
    "        return ord(str(num+1)[n%k-1]) - ord(\"0\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        base = 1\n",
    "        cont = 1\n",
    "        nums = 9\n",
    "        while n>nums:\n",
    "            n-=nums\n",
    "            cont*=10\n",
    "            base+=1\n",
    "            nums = 9*base*cont\n",
    "        numth = (n-1)//base + cont\n",
    "        poith = (n-1)%base\n",
    "        return int(str(numth)[poith])\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9\n",
    "        while n >= d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        \n",
    "        index = n - 1\n",
    "        num = 10 ** (d - 1) + index // d\n",
    "        digitIndex = index % d\n",
    "        return (num // 10 ** (d - 1 - digitIndex)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur, base = 1, 9\n",
    "        while n > cur * base:\n",
    "            n -= cur * base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "        n -= 1\n",
    "        ret = 10 ** (cur - 1) + n // cur\n",
    "        idx = n % cur\n",
    "        return ret // (10 ** (cur - 1 - idx)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9：9*1\n",
    "        # 10-99：90*2\n",
    "        # 100-999：900*3\n",
    "        # ...\n",
    "\n",
    "        if n<=9:return n\n",
    "\n",
    "        base, cur = 9, 1\n",
    "        while n>base:\n",
    "            cur +=1\n",
    "            n -= base\n",
    "            base = 9*10**(cur-1)*cur\n",
    "        \n",
    "        a, b = (n-1)//cur, (n-1)%cur\n",
    "\n",
    "        num = 10**(cur-1)+a\n",
    "        \n",
    "        return num//(10**(cur-b-1))%10\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n>count:\n",
    "            n=n-count\n",
    "            start=start*10\n",
    "            digit+=1\n",
    "            count=9*start*digit\n",
    "        num=start+(n-1)//digit\n",
    "        return int(str(num)[(n - 1) % digit])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, cnt = 1, 1, 9\n",
    "        while n>cnt:\n",
    "            n -= cnt\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            cnt = 9*start*digit\n",
    "        idx = (n-1)//digit\n",
    "        num = start + idx\n",
    "        return int(str(num)[(n-1)%digit])\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        cache = [0] * 40\n",
    "        self.cache2 = [10 ** i for i in range(33)]\n",
    "        res = 0\n",
    "        for i in range(1, 32 + 1):\n",
    "            # 计算代表有i+1个数字组成的整数，花了多少的数字位\n",
    "            max_num = self.cache2[i]\n",
    "            res += (max_num - (self.cache2[i-1])) * i\n",
    "            cache[i] = res\n",
    "        self.cache = cache\n",
    "    def cal_prepnum(self, x):\n",
    "            # 计算x前面有多少个数字\n",
    "            lenght = len(str(x))\n",
    "            # res = 0\n",
    "            # for i in range(1, lenght + 1):\n",
    "            #     # 计算代表有i+1个数字组成的整数，花了多少的数字位\n",
    "            #     max_num = min(10 ** i, x)\n",
    "            #     res += (max_num - (10 ** (i-1))) * i\n",
    "            res = self.cache[lenght - 1]\n",
    "            max_num = x\n",
    "            res += (max_num - (self.cache2[lenght-1])) * lenght\n",
    "            return res\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "\n",
    "        # 寻找是哪一个数字里的\n",
    "        # print(cal_prepnum(10))\n",
    "        # print(cal_prepnum(11))\n",
    "        left, right = 1, n\n",
    "        while left < right:\n",
    "            # print(left, right)\n",
    "            mid = (left + right + 1) // 2\n",
    "            cur_prep = self.cal_prepnum(mid)\n",
    "            if cur_prep >= n:\n",
    "                # mid前面的数字就大于n了\n",
    "                # 也就是说mid 和 mid 后面的都不可能\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                # mid前面的数字小于数量等于n\n",
    "                # 也就是说mid前面的数字不可能了\n",
    "                left = mid\n",
    "        \n",
    "        prep = self.cal_prepnum(left)\n",
    "        # print(left)\n",
    "        return int(str(left)[n - prep -1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count: # 1.\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit # 2.\n",
    "        return int(str(num)[(n - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit = 1\n",
    "        counter = 9\n",
    "        while n > counter:\n",
    "            n -= counter\n",
    "            digit += 1\n",
    "            counter = digit * pow(10, digit-1) * 9\n",
    "        pos_num = pow(10, digit-1) - 1 + n // digit\n",
    "        if n % digit == 0:\n",
    "            return int(str(pos_num)[-1])\n",
    "        else:\n",
    "            return int(str(pos_num+1)[n % digit-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, base = 1, 9\n",
    "        while n > digit * base:\n",
    "            n -= digit * base\n",
    "            digit += 1\n",
    "            base *= 10\n",
    "        \n",
    "        number = 10 **(digit - 1) + (n-1) //digit\n",
    "        #数字里第几位\n",
    "        idx = (n - 1) % digit\n",
    "        print(number,idx)\n",
    "        return int(str(number)[idx])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        ls = 1 # 字符串初始长度\n",
    "        base = 1\n",
    "        while base * 9 * ls < n:\n",
    "            n -= base * 9 * ls\n",
    "            ls += 1\n",
    "            base *= 10\n",
    "        start = 10**(ls-1) # 当前范围内的最小值\n",
    "        index = n - 1 # 当前位在开始位的索引，如果为10，应该是10-9后的第1位，索引为0\n",
    "        num = start + index // ls # 寻找第多少个数字\n",
    "        digit = index % ls  # 第多少个数字的第几位\n",
    "        print(f\"num:{num}, digit:{digit}, {num // (10**(ls-digit - 1))}\")\n",
    "        return (num // (10**(ls-digit - 1))) % 10\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        base = 9\n",
    "        bit_cnt = 1\n",
    "        while n > base * bit_cnt:\n",
    "            n -= base * bit_cnt\n",
    "            base *= 10\n",
    "            bit_cnt += 1\n",
    "        start = 10 ** (bit_cnt - 1)\n",
    "        idx = (n-1) // (bit_cnt)\n",
    "        offset = (n-1) % (bit_cnt)\n",
    "        return int(str(start + idx)[offset])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit\n",
    "        return int(str(num)[(n - 1) % digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        length = 1\n",
    "        while n:\n",
    "            ten = 10 ** (length - 1)\n",
    "            limit = ten * 9 * length \n",
    "            if n <= limit:\n",
    "                base = ten\n",
    "                plus = (n - 1) // length\n",
    "                mod = (n - 1) % length\n",
    "                num = base + plus\n",
    "                index = length - mod - 1\n",
    "                # print(\"n\",n,\"base\",base,\"plus\",plus,\"mod\",mod,\"index\",index,\"num\",num)\n",
    "                while index > 0:\n",
    "                    num //= 10\n",
    "                    index -= 1\n",
    "                return num % 10\n",
    "            else: n -= limit\n",
    "            length += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d = 1\n",
    "        count = 9\n",
    "        while n>d*count:\n",
    "            n -= d*count\n",
    "            d+=1\n",
    "            count*=10\n",
    "        s = str(10**(d-1)+(n-1)//d)\n",
    "        return int(s[n%d-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count: # 1.\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit += 1\n",
    "            count = 9 * start * digit\n",
    "        num = start + (n - 1) // digit # 2.\n",
    "        return int(str(num)[(n - 1) % digit]) # 3.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9：9*1\n",
    "        # 10-99：90*2\n",
    "        # 100-999：900*3\n",
    "        # ...\n",
    "\n",
    "        if n<=9:return n\n",
    "\n",
    "        base, cur = 9, 1\n",
    "        while n>base:\n",
    "            cur +=1\n",
    "            n -= base\n",
    "            base = 9*10**(cur-1)*cur\n",
    "        \n",
    "        a, b = (n-1)//cur, (n-1)%cur\n",
    "\n",
    "        num = 10**(cur-1)+a\n",
    "        \n",
    "        return num//(10**(cur-b-1))%10\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def totalDigits(self, length: int) -> int:\n",
    "        digits = 0\n",
    "        curCount = 9\n",
    "        for curLength in range(1, length + 1):\n",
    "            digits += curLength * curCount\n",
    "            curCount *= 10\n",
    "        return digits\n",
    "\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        low, high = 1, 9\n",
    "        while low < high:\n",
    "            mid = (low + high) // 2\n",
    "            if self.totalDigits(mid) < n:\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid\n",
    "        d = low\n",
    "        prevDigits = self.totalDigits(d - 1)\n",
    "        index = n - prevDigits - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d\n",
    "        digitIndex = index % d\n",
    "        return num // 10 ** (d - digitIndex - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        base = 9\n",
    "        digits = 1\n",
    "        while n - base * digits > 0:\n",
    "            n -= base * digits\n",
    "            base *= 10\n",
    "            digits += 1\n",
    "        idx = n % digits\n",
    "        if idx == 0:\n",
    "            idx = digits\n",
    "        number = 1\n",
    "        for i in range(1, digits):\n",
    "            number *= 10\n",
    "        if idx == digits:\n",
    "            number += n // digits - 1\n",
    "        else:\n",
    "            number += n // digits\n",
    "\n",
    "        for i in range(idx, digits):\n",
    "            number //= 10\n",
    "        return number % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9\n",
    "        while n > d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        index = n - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d\n",
    "        digitIndex = index % d\n",
    "        return num // 10 ** (d - digitIndex - 1) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n):\n",
    "        n -= 1\n",
    "        for digits in range(1, 11):\n",
    "            first_num = 10**(digits - 1)\n",
    "            if n < 9 * first_num * digits:\n",
    "                return int(str(first_num + n/digits)[n%digits])\n",
    "            n -= 9 * first_num * digits\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        if n <= 9:\n",
    "            return n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            temp = 9 * i * 10**(i-1)\n",
    "            if n > temp:\n",
    "                n -= temp\n",
    "            else:\n",
    "                break\n",
    "        begin = 10**(i-1) + n // i\n",
    "        n %= i\n",
    "        # print(begin)\n",
    "        return int(str(begin)[n-1]) if n > 0 else int(str(begin-1)[-1])\n",
    "\n",
    "        # print(n)\n",
    "        # return int(str(begin)[n-1])\n",
    "        # while n > 0:\n",
    "        #     temp = str(begin)\n",
    "        #     if n > len(temp):\n",
    "        #         n -= len(temp)\n",
    "        #     else:\n",
    "        #         return int(temp[n-1])\n",
    "        #     begin += 1\n",
    "        # return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        digit, start, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = 9 * digit * start\n",
    "        nums = start + (n - 1) // digit\n",
    "        return int(str(nums)[(n - 1) % digit])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9\n",
    "        while n > d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        \n",
    "        index = n - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d\n",
    "        digitIndex = index % d\n",
    "        return num // 10 ** (d - digitIndex - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        if n<=9 :\n",
    "            return n\n",
    "        n-= 9 \n",
    "        cur = 90\n",
    "        i = 2\n",
    "        while n>=i*cur:\n",
    "            n -= i*cur\n",
    "            i+=1\n",
    "            cur*=10\n",
    "        \n",
    "        temp = n//i - 1  + cur//9\n",
    "        if n%i == 0:\n",
    "            return temp % 10\n",
    "        temp+=1\n",
    "        return int(str(temp)[n%i-1])\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9：9*1\n",
    "        # 10-99：90*2\n",
    "        # 100-999：900*3\n",
    "        # ...\n",
    "\n",
    "        if n<=9:return n\n",
    "\n",
    "        base, cur = 9, 1\n",
    "        while n>base*cur:\n",
    "            n -= base*cur\n",
    "            cur +=1\n",
    "            base *=10\n",
    "\n",
    "        n -=1 \n",
    "        a, b = (n)//cur, (n)%cur\n",
    "\n",
    "        cur -=1 \n",
    "\n",
    "        num = 10**(cur)+a\n",
    "        \n",
    "        return num//(10**(cur-b))%10\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9：9*1\n",
    "        # 10-99：90*2\n",
    "        # 100-999：900*3\n",
    "        # ...\n",
    "\n",
    "        if n<=9:return n\n",
    "\n",
    "        base, cur = 9, 1\n",
    "        cur +=1\n",
    "        n -= base\n",
    "        base = 9*10**(cur-1)*cur\n",
    "        while n>base:\n",
    "            cur +=1\n",
    "            n -= base\n",
    "            base = 9*10**(cur-1)*cur\n",
    "        \n",
    "        a, b = (n-1)//cur, (n-1)%cur\n",
    "\n",
    "        num = 10**(cur-1)+a\n",
    "        \n",
    "        return num//(10**(cur-b-1))%10\n",
    "            \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # 1-9 10-99 100-999\n",
    "        # 9 2*90 3*900\n",
    "        cur,base = 1,9\n",
    "        while n - cur*base > 0:\n",
    "            n -= cur*base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "        n -= 1\n",
    "        # n是cur位数里的第n//cur个数的第n%cur位\n",
    "        num = 10**(cur - 1) + n//cur\n",
    "        return int(str(num)[n%cur])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d, count = 1, 9\n",
    "        while n > d * count:\n",
    "            n -= d * count\n",
    "            d += 1\n",
    "            count *= 10\n",
    "        index = n - 1\n",
    "        start = 10 ** (d - 1)\n",
    "        num = start + index // d\n",
    "        digitIndex = index % d\n",
    "        return num // 10 ** (d - digitIndex - 1) % 10\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        n = n\n",
    "        for i in range(20):\n",
    "            if n/((9*10**i) * (i+1)) >1:\n",
    "                #print(f'this:{n/(9*10**i)}')\n",
    "                n-=(9*10**i) * (i+1)\n",
    "            else:\n",
    "                \n",
    "                #print(n)\n",
    "                #print(i)#3\n",
    "\n",
    "                num = n // (i+1) #8341.25\n",
    "\n",
    "                num2 = num + 10**i - 1 #which number belongs to\n",
    "                mod = n % ( i+1)\n",
    "                #print(f'num:{num}, num2:{num2} mod:{mod}')\n",
    "                \n",
    "                if mod:\n",
    "                    return (num2+1) % 10**(i-mod+2) // 10**(i-mod+1)\n",
    "                    return int(str(num2+1)[mod-1])\n",
    "                else:\n",
    "                    return num2 % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur, base = 1, 9\n",
    "        while n > cur * base:\n",
    "            n -= cur * base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "        n -= 1\n",
    "        # 数字\n",
    "        num = 10 ** (cur - 1) + n // cur\n",
    "        # 数字里的第几位\n",
    "        idx = n % cur\n",
    "        return int(str(num)[idx])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        step = n\n",
    "        i = 0\n",
    "        while step > (i+1)*(10**(i+1) - 10**i):\n",
    "            step -= (i+1)*(10**(i+1) - 10**i)\n",
    "            i += 1\n",
    "        start = 10**i\n",
    "        a = (step-1)//(i+1)\n",
    "        b = (step-1)%(i+1)\n",
    "        return int(str(start+a)[b])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur, base = 1, 9\n",
    "        while n > cur * base:\n",
    "            n -= cur * base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "        n -= 1\n",
    "        # 数字\n",
    "        num = 10 ** (cur - 1) + n // cur\n",
    "        # 数字里的第几位\n",
    "        idx = n % cur\n",
    "        return num // (10 ** (cur - 1 - idx)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        n = n\n",
    "        for i in range(20):\n",
    "            if n/((9*10**i) * (i+1)) >1:\n",
    "                #print(f'this:{n/(9*10**i)}')\n",
    "                n-=(9*10**i) * (i+1)\n",
    "            else:\n",
    "                \n",
    "                print(n)\n",
    "                print(i)#3\n",
    "\n",
    "                num = n // (i+1) #8341.25\n",
    "\n",
    "                num2 = num + 10**i - 1 #which number belongs to\n",
    "                mod = n % ( i+1)\n",
    "                #print(f'num:{num}, num2:{num2} mod:{mod}')\n",
    "                \n",
    "                if mod:\n",
    "                    return int(str(num2+1)[mod-1])\n",
    "                else:\n",
    "                    return int(str(num2)[-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        count=9\n",
    "        i=1\n",
    "        start=1\n",
    "        while n>count:\n",
    "            n-=count\n",
    "            i+=1\n",
    "            start*=10\n",
    "            count=start*9*i\n",
    "        num=(n-1)//i+start\n",
    "        s=str(num)\n",
    "        return int(s[(n-1)%i])\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur = 9\n",
    "        i = 1\n",
    "        while n>=i*cur:\n",
    "            n -= i*cur\n",
    "            i+=1\n",
    "            cur*=10\n",
    "        \n",
    "        temp = n//i - 1  + cur//9\n",
    "        if n%i == 0:\n",
    "            return temp % 10\n",
    "        temp+=1\n",
    "        n%=i\n",
    "        return temp//(10**(i - n)) % 10\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        d=1\n",
    "        count=9\n",
    "        while n>d*count:\n",
    "            n-=d*count\n",
    "            d+=1\n",
    "            count*=10\n",
    "        index=n-1\n",
    "        start=10**(d-1)\n",
    "        num=start+index//d\n",
    "        digitIndex=index%d\n",
    "        #print(num)\n",
    "        #print(digitIndex)\n",
    "        return int(str(num)[digitIndex])\n",
    "        #return num//10**(d-digitIndex-1)%10\n",
    "        # d,count=1,9\n",
    "        # while n>d *count:\n",
    "        #     n-=d*count\n",
    "        #     d+=1\n",
    "        #     count*=10\n",
    "        # index=n-1\n",
    "        # start=10**(d-1)\n",
    "        # num=start+index//d\n",
    "        # digitIndex=index%d\n",
    "        # return num//10**(d-digitIndex-1)%10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        length = 1\n",
    "        while n:\n",
    "            ten = 10 ** (length - 1)\n",
    "            limit = ten * 9 * length \n",
    "            if n <= limit:\n",
    "                num = ten + (n - 1) // length\n",
    "                index = length - 1 - (n - 1) % length\n",
    "                # print(\"n\",n,\"base\",base,\"plus\",plus,\"mod\",mod,\"index\",index,\"num\",num)\n",
    "                # while index > 0:\n",
    "                #     num //= 10\n",
    "                #     index -= 1\n",
    "                num //= 10 ** index\n",
    "                return num % 10\n",
    "            else: n -= limit\n",
    "            length += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        start = 1\n",
    "        digit = 1\n",
    "        base = 9\n",
    "        while base < n:\n",
    "            n -= base\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            base = digit*start*9\n",
    "        number = start + (n-1)//digit \n",
    "        number_idx = (n-1)%digit\n",
    "        return int(str(number)[number_idx])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        count, digit, start = 9, 1, 1\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            digit += 1\n",
    "            start *= 10\n",
    "            count = start * 9 * digit\n",
    "        num = start + (n - 1) // digit\n",
    "        return int(str(num)[(n - 1) % digit])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        n = n\n",
    "        for i in range(20):\n",
    "            if n/((9*10**i) * (i+1)) >1:\n",
    "                #print(f'this:{n/(9*10**i)}')\n",
    "                n-=(9*10**i) * (i+1)\n",
    "            else:\n",
    "                \n",
    "                #print(n)\n",
    "                #print(i)#3\n",
    "\n",
    "                num = n // (i+1) #8341.25\n",
    "\n",
    "                num2 = num + 10**i - 1 #which number belongs to\n",
    "                mod = n % ( i+1)\n",
    "                #print(f'num:{num}, num2:{num2} mod:{mod}')\n",
    "                \n",
    "                if mod:\n",
    "                    return int(str(num2+1)[mod-1])\n",
    "                else:\n",
    "                    return num2 % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        start, digit_num, count = 1, 1, 9\n",
    "        while n > count:\n",
    "            n -= count\n",
    "            start *= 10\n",
    "            digit_num += 1\n",
    "            count = 9 * start * digit_num\n",
    "\n",
    "        num = (n-1) // digit_num + start\n",
    "        s = str(num)\n",
    "        v = s[(n-1) % digit_num]\n",
    "        return int(v)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        base = 9\n",
    "        digits = 1\n",
    "        while n - base * digits > 0:\n",
    "            n -= base * digits\n",
    "            base *= 10\n",
    "            digits += 1\n",
    "\n",
    "        idx = n % digits\n",
    "        if idx == 0:\n",
    "            idx = digits\n",
    "        number = 1\n",
    "        for i in range(1, digits):\n",
    "            number *= 10\n",
    "        if idx == digits:\n",
    "            number += n // digits - 1\n",
    "        else:\n",
    "            number += n // digits\n",
    "        for i in range(idx, digits):\n",
    "            number //= 10\n",
    "        return number % 10\n",
    "\n",
    "#https://leetcode-cn.com/problems/nth-digit/solution/xiang-jie-zhao-gui-lu-by-z1m/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        cur, base = 1, 9  # 位数\n",
    "        while n > cur * base:\n",
    "            n -= cur * base\n",
    "            cur += 1\n",
    "            base *= 10\n",
    "        n -= 1\n",
    "        # 数字\n",
    "        num = 10 ** (cur - 1) + n // cur\n",
    "        # 数字里的第几位\n",
    "        idx = n % cur\n",
    "        return num // (10 ** (cur - 1 - idx)) % 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        # n 位数字 有多少个\n",
    "        def n_nums(n):\n",
    "            return(9*(10**(n-1)))\n",
    "\n",
    "        \n",
    "        sum_last = 0\n",
    "        sum_cur = 9\n",
    "        n_weishu = 1\n",
    "        \n",
    "        while sum_cur < n:\n",
    "            sum_last = sum_cur\n",
    "            n_weishu += 1\n",
    "            sum_cur += (n_nums(n_weishu) * n_weishu)\n",
    "            \n",
    "        # 减去前一位数的所有积累长度，现在到了它的位数 的剩余长度\n",
    "        n_remaining = n - sum_last\n",
    "        \n",
    "        # 落在 当前位数 的第几个数字 的 第几个位数\n",
    "        n_rem_1 = n_remaining // n_weishu\n",
    "        n_rem_2 = n_remaining % n_weishu\n",
    "        \n",
    "        res = 10**(n_weishu-1)+(n_rem_1-1)\n",
    "        \n",
    "        if n_rem_2 == 0:\n",
    "            print('情况1', '落在几位数？', n_weishu, \n",
    "                  '真实数字',res,)\n",
    "            return( int( str(res)[-1] ) )\n",
    "        else:\n",
    "            res += 1\n",
    "            print('情况2', '落在几位数？', n_weishu, \n",
    "                  '真实数字',res, )\n",
    "            return( int( str(res)[n_rem_2-1] ) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        lenS = 1\n",
    "        start = 0\n",
    "        base = 1\n",
    "        while start + (lenS*9*(10**(lenS-1))) <= n:\n",
    "            start += lenS * 9 * (10**(lenS-1))\n",
    "            lenS += 1\n",
    "            base *= 10\n",
    "        # 当前数位长度为lenS\n",
    "        idx = n - start - 1\n",
    "        # 第几位数字\n",
    "        num = base + idx // lenS\n",
    "        # 第几位\n",
    "        k = idx % lenS\n",
    "        return num // (10**(lenS - k - 1)) % 10\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findNthDigit(self, n: int) -> int:\n",
    "        l,r=0,2**31\n",
    "        ans=0\n",
    "        ans_cnt=0\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            s=str(mid)\n",
    "            sl=len(s)\n",
    "            cnt=0\n",
    "            offset=0\n",
    "            for i in range(sl-1):\n",
    "                o=10**(i+1)-10**i\n",
    "                cnt+=(i+1)*o\n",
    "                offset+=o\n",
    "            cnt+=sl*(mid-offset)\n",
    "            print(l,r,mid,cnt,n)\n",
    "            if cnt<=n:\n",
    "                l=mid+1\n",
    "                ans=mid\n",
    "                ans_cnt=cnt\n",
    "            else:\n",
    "                r=mid\n",
    "        if ans_cnt<n:\n",
    "            ans+=1\n",
    "            s=str(ans)\n",
    "            ans_cnt+=len(s)\n",
    "        s=str(ans)\n",
    "        print('#',s,n,ans_cnt)\n",
    "        print('@',s,-(ans_cnt-n+1))\n",
    "        return int(s[-(ans_cnt-n+1)])\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
